Some data storage devices include a media cache. However, many data storage devices with media cache can suffer from inefficiency due to a random workload, which may require a significant amount of computation for analysis of the workload related to the media cache contents and may require a large amount of metadata to track the media cache contents. Thus, more efficient memory designs are needed.